use std::io;
/// 逆波兰表达式
fn main() {
    println!("输入表达式，例如：(3+7)*(3+4)");
    let mut input:String =String::new();
    io::stdin().read_line(&mut input).unwrap();
    let influx = influx(input);
    let ret = evaluate_rpn(&influx);
    println!("{}", ret.to_string());
}

fn influx(expr: String) -> String {
    // 转为逆波兰表达式的字符串
    let mut stack: Vec<char> = vec![];
    let mut numbers: Vec<char> = vec![];
    for c in expr.chars() {
        if '+' == c || '-' == c || '*' == c || '/' == c {
            if stack.is_empty() || *stack.last().unwrap() == '(' {
                stack.push(c);
            } else {
                /*
                反复从栈中弹出操作符并添加到逆波兰表达式列表中，直到栈为空、栈顶元素为左括号"("，
                或栈顶操作符的优先级低于当前操作符的优先级。然后将当前操作符压入栈中。
                */
                while !stack.is_empty()
                    || *stack.last().unwrap() != '('
                    || (['*', '/'].contains(stack.last().unwrap())) {
                    numbers.push(stack.pop().unwrap());
                }
            }
        } else if '(' == c {
            stack.push(c);
        } else if ')' == c {
            while let Some(c) = stack.pop() {
                numbers.push(c);
                if c == '(' {
                    numbers.pop();
                }
            }
        } else {
            numbers.push(c);
        }
    }

    for symbol in stack {
        numbers.push(symbol);
    }

    // println!("输入表达式={}", expr);
    let influx_expr: String = numbers.iter().map(|s| s.to_string() + " ").collect();
    println!("逆波兰表达式={}", influx_expr);
    influx_expr
}

fn evaluate_rpn(expression: &str) -> i32 {
    let mut stack: Vec<i32> = Vec::new();

    for token in expression.split_whitespace() {
        match token {
            "+" => {
                if let (Some(b), Some(a)) = (stack.pop(), stack.pop()) {
                    stack.push(a + b);
                } else {
                    panic!("Invalid expression");
                }
            }
            "-" => {
                if let (Some(b), Some(a)) = (stack.pop(), stack.pop()) {
                    stack.push(a - b);
                } else {
                    panic!("Invalid expression");
                }
            }
            "*" => {
                if let (Some(b), Some(a)) = (stack.pop(), stack.pop()) {
                    stack.push(a * b);
                } else {
                    panic!("Invalid expression");
                }
            }
            "/" => {
                if let (Some(b), Some(a)) = (stack.pop(), stack.pop()) {
                    stack.push(a / b);
                } else {
                    panic!("Invalid expression");
                }
            }
            _ => {
                if let Ok(number) = token.parse::<i32>() {
                    stack.push(number);
                } else {
                    panic!("Invalid token: {}", token);
                }
            }
        }
    }

    if let Some(result) = stack.pop() {
        if stack.is_empty() {
            return result;
        } else {
            panic!("Invalid expression");
        }
    } else {
        panic!("Invalid expression");
    }
}

